#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;

//string func()
//{
//	string ret;
//
//	return ret;
//}
//
//int main()
//{
//	string xx = func();
//
//	string s1;
//	cout << sizeof(s1) << endl;
//
//	string s2("1234");
//	cout << sizeof(s2) << endl;
//
//	string s3("11111111111111111111");
//	cout << sizeof(s3) << endl;
//
//	return 0;
//}


void test_vector1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector<int>::iterator it1 = v.begin();
	while (it1 != v.end())
	{
		cout << *it1 << endl;
		++it1;
	}
	cout << endl;

	for (const auto& e : v)
	{
		cout << e << endl;
	}
	cout << endl;

}

void test_vector2()
{
	vector<int> v1(10, 1);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	vector<int> v2(v1.begin(), v1.end());
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
}

void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	v.reserve(100);
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed:" << sz << '\n';
		}
	}

}

void test_vector3()
{
	TestVectorExpand();

	vector<int> v;
	for (size_t i = 0; i < 100; ++i)
	{
		v.push_back(i);
	}

	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.resize(10);
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.shrink_to_fit();
	cout << v.size() << endl;
	cout << v.capacity() << endl;

}

void test_vector4()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	//vector<int>::iterator it = v.begin();
	auto it = find(v.begin(), v.end(), 3);

	v.insert(it, 30);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	auto lit = find(lt.begin(), lt.end(), 3);

	if (lit != lt.end())
	{
		lt.insert(lit, 300);
	}

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//vector<string> vstr;
	//string s1("");
	//vstr.push_back(s1);
	//vstr.push_back(string(""));

	//vstr.push_back("");

	//for (const auto& e : vstr)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;

	//cout << vstr[0] << 'z' << endl;
	//cout << vstr[2] << endl;

}

//int main()
//{
//	//test_vector1();
//	//test_vector2();
//	//TestVectorExpand();
//
//	/*test_vector3();*/
//	test_vector4();
//
//	return 0;
//}


//int main()
//{
//	list<int> lt;
//	
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//	lt.push_back(5);
//
//	list<int>::iterator it = lt.begin();
//	while (it != lt.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	lt.reverse();
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;



void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	vector<int> v;

	for (size_t i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		v.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);


}

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	vector<int> v(lt2.begin(), lt2.end());
	sort(v.begin(), v.end());

	lt2.assign(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);

}

//int main()
//{
//	//test_op1();
//	//test_op2();
//
//	list<int> lt;
//
//
//	lt.push_back(1);
//	lt.push_back(4);
//	lt.push_back(2);
//	lt.push_back(2);
//	lt.push_back(1);
//	lt.push_back(1);
//
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	lt.sort();
//	lt.unique();
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//
//
//	return 0;
//
//}

int main()
{
	list<int> lt;


	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(1);
	lt.push_back(1);


	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.splice(lt.end(), lt,find(lt.begin(), lt.end(), 2));

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}